/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package dataStructure;

/**
 *
 * @author azouz
 */
public class BinaryTree {

    BinaryTree.Node root;

    public void addNode(int value) {
        if (root == null) {
            root = new Node(value);
        } else {
            root.add(value);
        }

    }

    public void showTree() {
        root.show(root);
    }

    public static void main(String args[]) {
        /*BinaryTree bt = new BinaryTree();
        bt.addNode(10);
        bt.addNode(11);
        bt.addNode(12);
        bt.addNode(13);
        bt.addNode(1);
        System.out.println(bt.search(13));
        System.out.println(bt.treeHieght());
        System.out.println(bt.isBalanced());
        BinaryTree bt2 = new BinaryTree();
        bt2.addNode(10);
        bt2.addNode(11);
        bt2.addNode(12);
        bt2.addNode(13);
        bt2.addNode(1);
        System.out.println("HEHE " + bt.isEqual(bt2));*/
        System.out.println(getDivionrepeats(1311, 20));

    }

    class Node {

        private int value;
        private Node rightNode;
        private Node leftNode;

        public Node(int value) {
            this.value = value;
        }

        public void add(int n) {
            if (n > this.value) {
                if (this.rightNode == null) {
                    this.rightNode = new Node(n);
                } else {
                    this.rightNode.add(n);
                }
            } else {
                if (this.leftNode == null) {
                    this.leftNode = new Node(n);
                } else {
                    this.leftNode.add(n);
                }
            }
        }

        /**
         * @return the rightNode
         */
        public Node getRightNode() {
            return rightNode;
        }

        /**
         * @param rightNode the rightNode to set
         */
        public void setRightNode(Node rightNode) {
            this.rightNode = rightNode;
        }

        /**
         * @return the leftNode
         */
        public Node getLeftNode() {
            return leftNode;
        }

        /**
         * @param leftNode the leftNode to set
         */
        public void setLeftNode(Node leftNode) {
            this.leftNode = leftNode;
        }

        /**
         * @return the value
         */
        public int getValue() {
            return value;
        }

        /**
         * @param value the value to set
         */
        public void setValue(int value) {
            this.value = value;
        }

        public void show(Node n) {
            if (n == null) {
                return;
            }
            System.out.println(n.value);
            show(n.getLeftNode());
            show(n.getRightNode());
        }

        public boolean search(Node n, int x) {
            if (n == null) {
                return false;
            }
            if (x == n.value) {
                return true;
            }
            if (x > n.value) {
                return this.search(n.getRightNode(), x);
            } else {
                return this.search(n.getLeftNode(), x);
            }

        }

        public int treeHieght(Node n) {
            if (n == null) {
                return 0;
            }
            return Math.max(this.treeHieght(n.getLeftNode()), this.treeHieght(n.getRightNode())) + 1;
        }

        public boolean isEqual(Node n, Node n2) {
            if (n == null && n2 == null) {
                return true;
            }
            if (n == null || n2 == null) {
                return false;
            }
            return (n.value == n2.value) && this.isEqual(n.getLeftNode(), n2.getLeftNode()) && this.isEqual(n.getRightNode(), n2.getRightNode());

        }
    }

    static String getDivionrepeats(int a, int b) {
        // Need to keep track of all previous quotients (q) and remainders (r).
        // Need a loop to generate q and r, as above.
        if (b == 0) {
            return "ILLEGAL b value";
        }

        int q = a / b;
        int r = a % b;
        StringBuilder patternString = new StringBuilder(String.valueOf(q));

        while (r != 0) {
            r *= 10;
            q = r / b;
            r = r % b;
            patternString.append(String.valueOf(q));
            if (patternString.toString().length() == 100) {
                return patternString.toString();
            }
            if (patternString.toString().length() > 100) {
                return patternString.substring(0, 100).toString();
            }
        }
        return patternString.toString();

    }

    public boolean search(int x) {
        return root.search(root, x);
    }

    public int treeHieght() {
        return root.treeHieght(root);
    }

    public boolean isBalanced() {
        System.out.println("LEFt : " + root.treeHieght(root.getLeftNode()));
        System.out.println("right: " + root.treeHieght(root.getRightNode()));
        if (Math.abs(root.treeHieght(root.getLeftNode()) - root.treeHieght(root.getRightNode())) <= 1) {
            return true;
        }
        return false;

    }

    public boolean isEqual(BinaryTree bt) {
        return root.isEqual(root, bt.root);
    }

}
